package E_2024;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

/*
    一个设备由N种类型元器件组成(每种类型元器件只需要一个，类型type编号从0~N-1),
    每个元器件均有可靠性属性reliability，可靠性越高的器件其价格price越贵。
    而设备的可靠性由组成设备的所有器件中可靠性最低的器件决定。给定预算S，
    购买N种元器件(每种类型元器件都需要购买一个)，在不超过预算的情况下，请给出能够组成的设备的最大可靠性.
输入描述
    S N
        S总的预算，N元器件的种类
    total
        元器件的总数，每种型号的元器件可以有多种: 此后有total行具体器件的数据
    type reliability price
        type 整数类型，代表元器件的类型编号从0 ~ N-1;
        reliability 整数类型，代表元器件的可靠性:
        price 整数类型，代表元器件的价格
输出描述
    符合预算的设备的最大可靠性，如果预算无法买产N种器件，则返回 -1
    备注
    0 <= S,price <= 10000000
    0 <= N <= 100
    0 <= type <= N-1
    0 <= total <= 100000
    0 < reliability <= 100000
例1：
    输入
    500 3
    6
    0 80 100
    0 90 200
    1 50 50
    1 70 210
    2 50 100
    2 60 150
    输出
    60
    预算500,设备需要3种元件组成，方案类型0的第一个(可靠性80),类型1的第二个(可靠性70),
    类型2的第二个(可靠性60),可以使设备的可靠性最大60
示例2
    输入
    100 1
    1
    0 90 200
    输出
    -1
    组成设备需要1个元件，但是元件价格大于预算，因此无法组成设备，返回-1
 */
public class E_200_12 {
    public static void main(String[] args) {
        ans(500,3, new int[][]{{0,80,100},{0,90,200},{1,50,50},{1,70,210},{2,50,100},{2,60,150}});
        System.out.println(ans);
        ans = -1;
        ans(100,1, new int[][]{{0,90,200}});
        System.out.println(ans);
    }
    public static int ans1(int S, int N, int[][] types){
        Arrays.sort(types, Comparator.comparing(a -> a[0]));
        int[][] ans = new int[S][N];
        int index = 0;
        for (int s = 0; s < S; s++) {
            for (int n = 0; n < N; n++) {
                for (;index < types.length; index++) {
                    int[] type = types[index];
                    if (type[0] != n) break;
                    if (n == 0)
                        ans[s][n] = type[1];
                }
            }
        }
        return -1;
    }
    public static int ans(int S, int N, int[][] types){
        Stack<Integer> stack = new Stack<>();
        temp(stack,types,N,S);
        return -1;
    }
    static int ans = -1;
    public static void temp(Stack<Integer> stack, int[][] types, int N, int S){
        if (stack.size() == N){
            int min = Integer.MAX_VALUE;
            int price = 0;
            for (Integer x : stack) {
                int[] temp = types[x];
                min = Math.min(temp[1], min);
                price += temp[2];
            }
            if (price <= S)
                ans = Math.max(ans,min);
            return;
        }
        for (int i = 0; i < types.length; i++) {
            int[] type = types[i];
            if (type[0] == stack.size()){
                stack.push(i);
                temp(stack,types,N,S);
                stack.pop();
            }
        }
    }
}
